package 力扣_链表.面试常考.环形链表;


/**
 * @author zx
 * @create 2022-09-12 13:02
 */
public class 环形链表II {
    /**
     * 走a+nb步一定是在环入口
     * 第一次相遇时慢指针已经走了nb步
     * 从head结点走到入环点需要走：a + nb,而slow已经走了nb,那么slow再走a步就是入环点
     * 构建一个新指针从head开始,和slow指针一起走,相遇时刚好就是a步
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode res = head;
                while(res != slow){
                    res = res.next;
                    slow = slow.next;
                }
                return res;//入环点相遇,返回入环点
            }
        }
        return null;
    }
}
class ListNode {
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
        next = null;
    }
}